package com.cplatform.cat;

import java.util.Stack;

public class MaxSquera {
    public static void main(String[] args) {
        int[] heights = new int[]{4,2,0,3,2,4,3,4};
        largestRectangleArea2(heights);

    }
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if(len < 1){
            return 0;
        }
        int max = 0;
        for(int i = 0;i < len;i++){
            int height = heights[i];
            int left = i;
            while(left > 0 && height <= heights[left-1]){
                left--;
            }
            int right = i;
            while(right < len-1 && height <= heights[right+1]){
                right++;
            }
            max = Math.max(max,height * (right - left + 1));

        }
        return max;

    }
    public static int largestRectangleArea2(int[] heights) {
        int len = heights.length;
        if(len < 1){
            return 0;
        }
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < len;i++){
            //单调性递增的栈
            while(!stack.empty() && heights[i] < heights[stack.peek()]){
                int currHeight = heights[stack.pop()];
                int currWidth;
                if(stack.empty()){
                    currWidth = i;
                }else{
                    currWidth = i - stack.peek() - 1;
                }
                max = Math.max(max,currHeight * currWidth);
            }
            stack.push(i);
        }
        //清空队列
        while(!stack.empty()){
            int currHeight = heights[stack.pop()];
            int currWidth;
            if(stack.empty()){
                currWidth = len;
            }else{
                currWidth = len - stack.peek() - 1;
            }
            max = Math.max(max,currHeight * currWidth);
        }
        return max;

    }
}
